__author__ = 'st316'
'''
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4],
the contiguous subarray [4, -1, 2, 1] has the largest sum = 6.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach,
which is more subtle.
'''


class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxSubArray(self, A):
        if not A:
            return 0
        maxSum = A[0]
        curSum = 0
        for a in A:
            if curSum >= 0:
                curSum += a
            else:
                curSum = a
            if curSum > maxSum:
                    maxSum = curSum
        return maxSum


if __name__ == '__main__':
    s = Solution()
    print s.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])